package xyz.scootaloo.oj.offer;

import org.junit.Test;
import xyz.scootaloo.oj.ds.TreeNode;

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 9:44
 */
public class P68II {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = null;
        if (root.left != null) {
            res = dfs(root.left, p, q);
            if (res != null)
                return res;
        }
        if (root.right != null) {
            res = dfs(root.right, p, q);
            if (res != null)
                return res;
        }
        if (findAndMatch(root, p) && findAndMatch(root, q)) {
            return root;
        } else {
            return null;
        }
    }

    private boolean findAndMatch(TreeNode root, TreeNode node) {
        if (root == node)
            return true;
        return (root.left != null && findAndMatch(root.left, node)) ||
                (root.right != null && findAndMatch(root.right, node));
    }

    @Test
    public void testFunc() {
        TreeNode node6 = new TreeNode(6);
        TreeNode node2 = new TreeNode(2);
        TreeNode node8 = new TreeNode(8);
        TreeNode node0 = new TreeNode(0);
        TreeNode node4 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node3 = new TreeNode(3);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);

        node3.left = node5;
        node3.right = node1;

        node5.left = node6;
        node5.right = node2;

        node2.left = node7;
        node2.right = node4;

        node1.left = node0;
        node1.right = node8;

        System.out.println(lowestCommonAncestor(node3, node5, node1));
        System.out.println(lowestCommonAncestor(node3, node5, node4));
        System.out.println(lowestCommonAncestor(node3, node0, node8));
        System.out.println(lowestCommonAncestor(node3, node1, node8));
    }

}
